テーマ：アルゴリズム設計としての分割統治法
正解はこちら
解答：ウ
[基礎知識・用語のまとめ]
分割統治法・・・問題全体をいくつかの小さな問題に分割して、分割されたそれぞれの問題を独立して処理した結果を結合することによって、最終的に元の問題全体を解決する手法です。
[解法]
分割統治法では、以下の手順１～３で設計を進めます。
手順１：分割（問題全体を小さな問題に分割する）
手順２：統治（小さな問題をそれぞれ解く）
手順３：組合せ（小さな問題の解を組み合わせて、問題全体の解を求める）
問題全体を小さく分割することで、解決しなければならない項目が絞られ、検討する範囲も小さくなることから、問題全体を一度に解決することに比べて解決が容易になります。正解の選択肢は「ウ」となります。
他の選択肢については、以下の通りです。
ア→局所探索法の説明です。とりあえず粗い解を出し、それを逐次改良して、精度の高い解を得るのがポイントです。
イ→組み合わせ最適化問題のアルゴリズムの説明です。解くために膨大な計算量を必要とする巡回セールスマン問題などの解を解くために適用される手法です。
エ→貧欲法の説明です。各時点で最良の解を選択していく点がポイントです。
[参考]
分割統治法の典型的な例として”マージソート”がよくあげられる、、、らしい。
利用させていただきました素材へのリンク
うさちゃこちゃんねる様 https://www.youtube.com/channel/UCQcDdg4W6r5OfcB1JTcpABw
ここまで読んでくれてありがとう！！
感謝！
コメント